347. 前 K 个高频元素

mid

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

堆

维护一个小顶堆

import "container/heap"

func topKFrequent(nums []int, k int) []int {
	hash := map[int]int{}
	//记录每个元素出现的次数
	for _, num := range nums {
		hash[num]++
	}
	
	h := &Heap{}
	heap.Init(h)
	//所有元素入堆，堆的长度为k
	for val, frequency := range hash {
		heap.Push(h, node{val, frequency})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	res := make([]int, k)
	//按顺序返回堆中的元素
	for i := 0; i < k; i++ {
		res[k-i-1] = heap.Pop(h).(node).val
	}
	return res
}

type node struct {
	val       int
	frequency int
}

//构建小顶堆
type Heap []node

func (h Heap) Len() int {
	return len(h)
}

func (h Heap) Less(i, j int) bool {
	return h[i].frequency < h[j].frequency
}

func (h Heap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *Heap) Push(x interface{}) {
	*h = append(*h, x.(node))
}
func (h *Heap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

347. 前 K 个高频元素

堆​

堆